package com.leetcode.根据算法进行分类.位运算相关;

import java.util.HashSet;

/**
 * @author: ZhouBert
 * @date: 2021/3/4
 * @description: 剑指 Offer 56 - II. 数组中数字出现的次数 II
 * https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/
 */
public class B_剑指Offer56II_数组中数字出现的次数II {

	static B_剑指Offer56II_数组中数字出现的次数II action = new B_剑指Offer56II_数组中数字出现的次数II();

	public static void main(String[] args) {
		test1();
	}

	public static void test1() {
		int[] nums = new int[]{3, 4, 3, 3};
		int res = action.singleNumber(nums);
		System.out.println("res = " + res);
	}

	/**
	 * 这个思路在题解里也算比较少见的：
	 * sum = 3x+y;
	 * partSum = x+y
	 * => res= (3*partSum - sum) /2
	 * @param nums
	 * @return
	 */
	public int singleNumber(int[] nums) {
		HashSet<Integer> set = new HashSet<>();
		int len = nums.length;
		long sum = 0;
		long partSum = 0;
		for (int i = 0; i < len; i++) {
			sum += nums[i];
			if (set.contains(nums[i])) {
				partSum -= nums[i];
				set.remove(nums[i]);
			} else {
				partSum += nums[i];
				set.add(nums[i]);
			}
		}
		return (int) ((partSum + (partSum << 1) - sum) >> 1);
	}
}
